package Demo1021;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.Arrays;

/**
 * 双边快排循环
 * @author Knife
 */
public class QuickSortDouble {
    public static void main(String[] args) {
        int [] arr = new int[]{5,9,6,4,1,8,7,2,3};
        quick(arr,0,arr.length-1);
    }
    public static void quick(int [] arr, int l, int h){
        if (l>=h){
            return;
        }
        int p = partition(arr, l, h);
        quick(arr,l,p-1);
        quick(arr,p+1,h);
    }
    private static int partition(int[] arr, int l, int h) {
        int pv = arr[l];
        int i = l;
        int j = h;
        while (i<j){
            // 先从右往左进行查找
            //todo : i<j &&
            while (i<j && arr[j]>pv){
                j--;
            }
            //todo : <= 防止把基准点元素交换走了
            while (i<j && arr[i]<=pv){
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,l,i);
        System.out.println(Arrays.toString(arr)+",i="+i);
        return j;
    }
    public static void swap(int[] arr,int i,int j){
        int temp ;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
